package leetcode.code1190;

import leetcode.IDebug;
import leetcode.helper.HelpDebug;

//执行用时：1 ms, 在所有 Java 提交中击败了99.18%的用户
//
//内存消耗：39.8 MB, 在所有 Java 提交中击败了5.09%的用户
//
//通过测试用例：38 / 38

public class Solution2 implements IDebug {

	int len;

	public String reverseParentheses(String s) {
		char[] cs = s.toCharArray();
		len = cs.length;
//		Stack<Object[]> stack = new Stack<>();
//		stack.add(new Object[] { 0, false });
//		while (!stack.isEmpty()) {
//			Object[] cur = stack.pop();
//			int index = (int) cur[0];
//			boolean reverse = (boolean) cur[1];
//			int p = index;
//			StringBuffer sb = new StringBuffer();
//			while (p < len) {
//				char c = cs[p];
//				if (c == '(') {
//					Object[] res = this.f(cs, p + 1, !reverse);
//					if (!reverse) {
//						sb.append(String.valueOf(res[0]));
//					} else {
//						sb.insert(0, String.valueOf(res[0]));
//					}
//					p = (int) res[1] + 1;
//				} else if (c == ')') {
//					return new Object[] { sb.toString(), p };
//				} else {
//					if (!reverse) {
//						sb.append(c);
//					} else {
//						sb.insert(0, c);
//					}
//					p++;
//				}
//			}
//		}
		return (String) f(cs, 0, false)[0];
	}

	private Object[] f(char[] cs, int index, boolean reverse) {
		if (index == len) {
			return new Object[] { "", index };
		}
		int p = index;
		StringBuffer sb = new StringBuffer();
		while (p < len) {
			char c = cs[p];
			if (c == '(') {
				Object[] res = this.f(cs, p + 1, !reverse);
				if (!reverse) {
					sb.append(String.valueOf(res[0]));
				} else {
					sb.insert(0, String.valueOf(res[0]));
				}
				p = (int) res[1] + 1;
			} else if (c == ')') {
				return new Object[] { sb.toString(), p };
			} else {
				if (!reverse) {
					sb.append(c);
				} else {
					sb.insert(0, c);
				}
				p++;
			}
		}
		return new Object[] { sb.toString(), p };
	}

	@Override
	public void debug1() {
		HelpDebug.compare("dcba", this.reverseParentheses("(abcd)"));

	}

	@Override
	public void debug2() {
		// TODO Auto-generated method stub

		HelpDebug.compare("iloveu", this.reverseParentheses("(u(love)i)"));
	}

	@Override
	public void debug3() {
		// TODO Auto-generated method stub
		HelpDebug.compare("leetcode", this.reverseParentheses("(ed(et(oc))el)"));
	}

	@Override
	public void debug4() {
		// TODO Auto-generated method stub
		HelpDebug.compare("apmnolkjihgfedcbq", this.reverseParentheses("a(bcdefghijkl(mno)p)q"));
	}

	public static void main(String[] args) {
		Solution2 so = new Solution2();
		so.debug1();
		so.debug2();
		so.debug3();
		so.debug4();

	}

}
